/*在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。
*
* 输入: [3,2,1,5,6,4] 和 k = 2
* 输出: 5
* */

package newcoder.Heap_2;

public class Leetcode215 {

    public static void main(String[] args) {

        Leetcode215 obj = new Leetcode215();
        int[] nums = {3,2,1,5,6,4};
        int k = 2;
        System.out.println(obj.findKthLargest(nums, k));
    }

    public int findKthLargest(int[] nums, int k){

        int len = nums.length;
        //构建小顶堆之后，堆顶元素一定是最小的
        buildMinHeap(nums, len);

        for (int i = len - 1;i >= 0;i--){
            //将最小元素与数组最后一个数字交换位置，剩下的继续调整堆，再取出最小元素
            swap(nums, 0, i);
            len--;
            adjustHeap(nums, 0, i);
        }
        return nums[k - 1];
    }

    //构建一个小顶堆
    public void buildMinHeap(int[] nums, int len){

        for (int i = (int)Math.floor(len / 2); i >= 0;i--){
            adjustHeap(nums, i, len);
        }
    }

    public void adjustHeap(int[] nums, int i, int len){

        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int min = i;
        if (left < len && nums[left] < nums[min]){
            min = left;
        }
        if (right < len && nums[right] < nums[min]){
            min = right;
        }
        if (min != i){
            swap(nums, i, min);
            adjustHeap(nums, min, len);
        }

    }

    public void swap(int[] nums, int i, int j){

        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
